//21. 合并两个有序链表

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

#include <stdio.h>

struct ListNode 
{
    int val;
    struct ListNode *next;
};
 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    //若有一个链表为空，返回另一个链表
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;

    struct ListNode* newhead = list1;
    struct ListNode* prev = NULL;

    // 当两个链表都非空时循环
    while(list1 && list2)
    {
        // list1节点更小，更新prev，并移动list1至下一个节点
        if(list1->val <= list2->val)
        {
            prev = list1;
            list1 = list1->next;
        }
        // list2节点更小
        else
        {
            struct ListNode* temp = list2;
            list2 = list2->next;

             // 若prev为空（初始状态），更新头节点
            if(!prev)
            {
                temp->next = list1;
                newhead = temp;
            }
            // 若prev不为空，出入到temp与prev中间
            else
            {
                temp->next = list1;
                prev->next = temp;
            }
            prev = temp;    // 更新prev为插入的节点

        }
    }

    // 若list2有剩余节点，直接接到prev后面
    if(list2)
    {
        prev->next = list2;
    }

    return newhead;
}